package com.dong.ListNode.arithemtic;

import java.util.ArrayList;
import java.util.LinkedList;
/**
 *设计单链表
 */
class ListNode2 {
    //节点值
    int val;
    //下一个节点
    ListNode2 next;
    ListNode2() {}
    ListNode2(int val) { this.val = val; }
    ListNode2(int val, ListNode2 next) { this.val = val; this.next = next; }
}
public class ListNodeDemo2 {
    //size存储表元素的个数
    int size;
    //虚拟头结点
    ListNode2 head;

    //初始化链表
    public ListNodeDemo2() {
        size=0;
        head=new ListNode2(0);
    }


    //获取index节点的数值
    public int get(int index){
        //如果index非法，返回-1
        if (index<0||index>size){
            return -1;
        }
        //设置一个当前节点
        ListNode2 currentNode =head;
        for (int i = 0; i <= index; i++) {
            currentNode = currentNode.next;
        }
        return currentNode.val;
    }

    // 在第 index 个节点之前插入一个新节点，例如index为0，那么新插入的节点为链表的新头节点。
    // 如果 index 等于链表的长度，则说明是新插入的节点为链表的尾结点
    // 如果 index 大于链表的长度，则返回空
    public void addAtIndex(int index, int val) {
        if (index>size){
            return;
        }
        if (index<0){
            index=0;
        }
        size++;
        //找到要插入节点得前驱
        ListNode2 pred =head;
        for (int i = 0; i < index; i++) {
            pred = pred.next;
        }
        ListNode2 toAdd = new ListNode2(val);
        //将前后得链条链接起来
        toAdd.next = pred.next;
        pred.next = toAdd;
    }


    //在链表最前面插入一个节点
    public void addAtIndex(int val) {
        addAtIndex(0, val);
    }

    //在链表的最后面插入一个节点
    public void addTail(int val){
        addAtIndex(size,val);
    }

    //删除链表的的第Index节点
    public void deleteAtIndex(int index) {
        if(index<0||index>size){
            return;
        }
        size--;
        ListNode2 pred = head;
        //遍历到第index节点的前一个节点
        for (int i = 0; i < index; i++) {
            pred = pred.next;
        }

        pred.next = pred.next.next;


    }
}



